翻訳と辞書 Words near each other ・ "O" Is for Outlaw ・ "O"-Jung.Ban.Hap. ・ "Ode-to-Napoleon" hexachord ・ "Oh Yeah!" Live ・ "Our Contemporary" regional art exhibition (Leningrad, 1975) ・ "P" Is for Peril ・ "Pimpernel" Smith ・ "Polish death camp" controversy ・ "Pro knigi" ("About books") ・ "Prosopa" Greek Television Awards ・ "Pussy Cats" Starring the Walkmen ・ "Q" Is for Quarry ・ "R" Is for Ricochet ・ "R" The King (2016 film) ・ "Rags" Ragland ・ ! (album) ・ ! (disambiguation) ・ !! ・ !!! ・ !!! (album) ・ !!Destroy-Oh-Boy!! ・ !Action Pact! ・ !Arriba! La Pachanga ・ !Hero ・ !Hero (album) ・ !Kung language ・ !Oka Tokat ・ !PAUS3 ・ !T.O.O.H.! ・ !Women Art Revolution Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Kleene fixpoint theorem ： ウィキペディア英語版 Kleene fixed-point theorem In the mathematical areas of order and lattice theory, the Kleene fixed-point theorem, named after American mathematician Stephen Cole Kleene, states the following: :''Let (L, ⊑) be a CPO (complete partial order), and let f : L → L be a Scott-continuous (and therefore monotone) function. Then f has a least fixed point, which is the supremum of the ascending Kleene chain of f. The ascending Kleene chain of ''f'' is the chain :$\backslash bot\; \backslash ;\; \backslash sqsubseteq\; \backslash ;\; f(\backslash bot)\; \backslash ;\; \backslash sqsubseteq\; \backslash ;\; f\backslash left(f(\backslash bot)\backslash right)\; \backslash ;\; \backslash sqsubseteq\; \backslash ;\; \backslash dots\; \backslash ;\; \backslash sqsubseteq\; \backslash ;\; f^n(\backslash bot)\; \backslash ;\; \backslash sqsubseteq\; \backslash ;\; \backslash dots$ obtained by iterating ''f'' on the least element ⊥ of ''L''. Expressed in a formula, the theorem states that :$\backslash textrm(f)\; =\; \backslash sup\; \backslash left(\backslash left\backslash \backslash right)$ where $\backslash textrm$ denotes the least fixed point. This result is often attributed to Alfred Tarski, but Tarski's fixed point theorem pertains to monotone functions on complete lattices. == Proof == We first have to show that the ascending Kleene chain of ''f'' exists in L. To show that, we prove the following lemma: :Lemma 1:''If L is CPO, and f : L → L is a Scott-continuous function, then $f^n(\backslash bot)\; \backslash sqsubseteq\; f^(\backslash bot),\; n\; \backslash in\; \backslash mathbb\_0$ Proof by induction: * Assume n = 0. Then $f^0(\backslash bot)\; =\; \backslash bot\; \backslash sqsubseteq\; f^1(\backslash bot)$, since ⊥ is the least element. * Assume n > 0. Then we have to show that $f^n(\backslash bot)\; \backslash sqsubseteq\; f^(\backslash bot)$. By rearranging we get $f(f^(\backslash bot))\; \backslash sqsubseteq\; f(f^n(\backslash bot))$. By inductive assumption, we know that $f^(\backslash bot)\; \backslash sqsubseteq\; f^n(\backslash bot)$ holds, and because f is monotone (property of Scott-continuous functions), the result holds as well. Immediate corollary of Lemma 1 is the existence of the chain. Let $\backslash mathbb$ be the set of all elements of the chain: $\backslash mathbb\; =\; \backslash$. This set is clearly a directed/ω-chain, as a corollary of Lemma 1. From definition of CPO follows that this set has a supremum, we will call it $m$. What remains now is to show that $m$ is the least fixed-point. First, we show that $m$ is a fixed point, i.e. that $f(m)\; =\; m$. Because $f$ is Scott-continuous, $f(\backslash sup(\backslash mathbb))\; =\; \backslash sup(f(\backslash mathbb))$, that is $f(m)\; =\; \backslash sup(f(\backslash mathbb))$. Also, since $f(\backslash mathbb)\; =\; \backslash mathbb\backslash setminus\backslash$ and because $\backslash bot$ has no influence in determining $\backslash sup$, we have that $\backslash sup(f(\backslash mathbb))\; =\; \backslash sup(\backslash mathbb)$. It follows that $f(m)\; =\; m$, making $m$ a fixed-point of $f$. The proof that $m$ is in fact the ''least'' fixed point can be done by showing that any Element in $\backslash mathbb$ is smaller than any fixed-point of $f$ (because by property of supremum, if all elements of a set $D\; \backslash subseteq\; L$ are smaller than an element of $L$ then also $\backslash sup(D)$ is smaller than that same element of $L$). This is done by induction: Assume $k$ is some fixed-point of $f$. We now prove by induction over $i$ that $\backslash forall\; i\; \backslash in\; \backslash mathbb\backslash colon\; f^i(\backslash bot)\; \backslash sqsubseteq\; k$. For the induction start, we take $i\; =\; 0$: $f^0(\backslash bot)\; =\; \backslash bot\; \backslash sqsubseteq\; k$ obviously holds, since $\backslash bot$ is the smallest element of $L$. As the induction hypothesis, we may assume that $f^i(\backslash bot)\; \backslash sqsubseteq\; k$. We now do the induction step: From the induction hypothesis and the monotonicity of $f$ (again, implied by the Scott-continuity of $f$), we may conclude the following: $f^i(\backslash bot)\; \backslash sqsubseteq\; k\; ~\backslash implies~\; f^(\backslash bot)\; \backslash sqsubseteq\; f(k)$. Now, by the assumption that $k$ is a fixed-point of $f$, we know that $f(k)\; =\; k$, and from that we get $f^(\backslash bot)\; \backslash sqsubseteq\; k$. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Kleene fixed-point theorem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.